1. Technical Field
The invention is related to the encoding and subsequent decoding of bi-level images, and more particularly to a system and process for encoding and decoding bi-level images that uses two context-based adaptive modules: 1) an adaptive predictor controlled by low-resolution probability estimates that is used to map the original pixels explicitly into prediction error pixels, and 2) a backward-adaptive Run-Length-Rice (RLR) coder that encodes the prediction error pixels.
2. Background Art
Bi-level images are quite common in digital document processing, because they offer the potential for a compact representation of black-and-white documents containing texts and drawings. In such images, their picture elements (pixels) can be seen as coming from a binary source (e.g., white=“0” and black=“1”). Since they usually contain a lot of white space and repeated ink patterns, one basic approach to efficiently encode such images is to scan them in raster order, e.g., from top to bottom and left to right, and encode each pixel via adaptive arithmetic coding (AC), whose state (or probability table) is controlled by a context formed by the values of the pixels in a small template enclosing previously encoded pixels [1]. That idea is the basis of most modern bi-level image compression systems.
Facsimile images are usually transmitted using the old CCITT standards T.4 and T.6, which are usually referred to as Group 3 and Group 4 respectively. G3 usually encodes images with a modified Huffman (MH) code (i.e., Huffman coding on runs of black or white pixels), and G4 uses MMR coding. MH and MMR are not as efficient as context-adaptive AC, but are simpler to implement. Over time, G3 and G4 evolved to include encoding via JBIG (also known as recommendation T.82). JBIG uses the context-adaptive AC, with adaptive templates and the efficient QM binary arithmetic encoder [2]. The JBIG-2 standard extends JBIG by including pattern matching for text and halftone data, as well as soft pattern matching (SPM) [3] for lossy encoding. The JB2 encoder [4] is also based on SPM, but uses the Z-coder for binary encoding. JBIG, JBIG-2 and JB2 can provide a significant improvement in compression performance over G4.
Although arithmetic coding is usually the choice when high compression performance is desired, comparable performance can be achieved by appropriate refinements to run-length (RL) coders. The Z-coder and the adaptive TRL coder are examples of efficient RL variants.
It is noted that in this background section and in the remainder of the specification, the description refers to various individual publications identified by a numeric designator contained within a pair of brackets. For example, such a reference may be identified by reciting, “reference [1]” or simply “[1]”. A listing of the publications corresponding to each designator can be found at the end of the Detailed Description section.